
from cProfile import label

import graphviz
import gc

# 定义一个简单的状态类
class NFAState:
    def __init__(self, id):
        self.id = id
        self.transitions = {}

    def add_transition(self, symbol, state):
        if symbol not in self.transitions:
            self.transitions[symbol] = []
        self.transitions[symbol].append(state)

# 定义一个简单的NFA类
class NFA:
    def __init__(self):
        self.states = []
        self.state_count = 0  # 用于状态编号
        self.start_state = None
        self.accept_state = None

    def new_state(self, id=None):
        # 如果 id 参数存在，直接用给定的 id 生成状态
        if id is None:
            id = self.state_count
        self.state_count += 1
        state = NFAState(id)
        self.states.append(state)
        return state

    def increment_state_ids(self, nfa, left, right, increment=1):
        # 将给定NFA的所有状态 id 递增
        print('before adding')
        for state in nfa.states:
            print(state.id, end=',')
            if left <= state.id <= right:
                state.id += increment
        print()
        print('after adding')
        for state in nfa.states:
            print(state.id, end=',')
        print()


    # def get_min_state_id(self, nfa):
    #     # 返回给定NFA的最小状态 id
    #     return min(state.id for state in nfa.states)

    def visualize(self):
        dot = graphviz.Digraph()
        dot.attr(rankdir='LR')  # 设置从左到右的布局方向
        dot.graph_attr['dpi'] = '1000'

        # 创建一个隐式的起始节点，并且没有标签和形状
        dot.node("start", shape="none", label="")  # 隐式起点

        # 设定起始状态为S0，终止状态为最后编号的状态
        dot.node(f"S{self.start_state.id}", shape='circle', label=f"S{self.start_state.id}")  # 起点
        dot.node(f"S{self.accept_state.id}", shape='doublecircle', label=f"S{self.accept_state.id}")  # 终点

        # 绘制从隐式起点指向S0的空箭头
        dot.edge("start", f"S{self.start_state.id}", label="Start")

        # 按顺序绘制每个中间状态
        for state in self.states:
            if state != self.start_state and state != self.accept_state:
                dot.node(f"S{state.id}", shape='circle', label=f"S{state.id}")

        # 绘制状态之间的边
        for state in self.states:
            for symbol, next_states in state.transitions.items():
                for next_state in next_states:
                    dot.edge(f"S{state.id}", f"S{next_state.id}", label=symbol)

        # 保存并渲染图像
        dot.render("nfa", format="png", cleanup=False)
        return dot


# 解析正则表达式并生成NFA
class RegexToNFAConverter:
    def __init__(self, regex):
        self.regex = regex
        self.pos = 0
        self.nfa = NFA()

    def parse(self):
        # 解析整个正则表达式
        return self.expression()

    def expression(self):
        nfa = self.term()
        while self.pos < len(self.regex) and self.regex[self.pos] == '|':
            self.pos += 1  # 跳过 '|'
            nfa2 = self.term()
            nfa = self.union(nfa, nfa2)
        return nfa

    def term(self):
        nfa = self.factor()
        while self.pos < len(self.regex) and self.regex[self.pos] not in '|)':
            nfa2 = self.factor()
            nfa = self.concat(nfa, nfa2)  # 处理串联，避免多余状态
        return nfa

    def factor(self):
        nfa = self.base()
        while self.pos < len(self.regex) and self.regex[self.pos] == '*':
            self.pos += 1  # 跳过 '*'
            nfa = self.kleene_star(nfa)
        return nfa

    def base(self):
        if self.regex[self.pos] == '(':
            self.pos += 1  # 跳过 '('
            nfa = self.expression()
            self.pos += 1  # 跳过 ')'
            return nfa
        else:
            return self.single_char()

    def single_char(self):
        # 处理单个字符
        char = self.regex[self.pos]
        self.pos += 1
        start = self.nfa.new_state()
        end = self.nfa.new_state()
        start.add_transition(char, end)
        return self.build_nfa(start, end)

    def kleene_star(self, nfa):
        # 处理 Kleene 星号 '*'
        # 获取子NFA的最小状态 id
        min_id = nfa.start_state.id
        max_id = nfa.accept_state.id
        print('min_id:', min_id, 'max_id:', max_id)
        # 将所有状态 id 递增 1
        self.nfa.increment_state_ids(nfa,left = min_id, right = max_id, increment=1)
        # 创建新的起始状态，id 为子NFA的最小 id
        start = self.nfa.new_state(id=min_id)
        end = self.nfa.new_state()
        # ε 转换从起点到子表达式的起点，从子表达式的终点到终点
        start.add_transition('ε', nfa.start_state)
        nfa.accept_state.add_transition('ε', end)
        # ε 转换用于回环
        start.add_transition('ε', end)
        nfa.accept_state.add_transition('ε', nfa.start_state)
        # 返回包含子表达式的整体NFA
        return self.build_nfa(start, end)

    def union(self, nfa1, nfa2):
        # 处理 '|' 操作符
        # 获取两个子 NFA 的最小状态 id
        min_id = min(nfa1.start_state.id, nfa2.start_state.id)
        max_id = max(nfa1.accept_state.id, nfa2.accept_state.id)
        print('nfa1.start_state.id:',nfa1.start_state.id,'nfa2.start_state.id:', nfa2.start_state.id)
        print('nfa1.accept_state.id:',nfa1.accept_state.id,'nfa2.accept_state.id:', nfa2.accept_state.id)
        print('min_id:', min_id, 'max_id:', max_id)
        # 递增 nfa1 和 nfa2 的所有状态 id
        self.nfa.increment_state_ids(nfa1, left=min_id, right=max_id, increment=1)
        # self.nfa.increment_state_ids(nfa2, increment=1)
        start = self.nfa.new_state(id=min_id)
        end = self.nfa.new_state()
        start.add_transition('ε', nfa1.start_state)
        start.add_transition('ε', nfa2.start_state)
        nfa1.accept_state.add_transition('ε', end)
        nfa2.accept_state.add_transition('ε', end)
        return self.build_nfa(start, end)

    def concat(self, nfa1, nfa2):
        # 将 nfa2.start_state 的所有转移合并到 nfa1.accept_state
        # min_id = max(nfa1.start_state.id, nfa2.start_state.id)
        min_id = nfa2.start_state.id
        max_id = nfa2.accept_state.id
        print('nfa1.start_state.id:', nfa1.start_state.id, 'nfa2.start_state.id:', nfa2.start_state.id)
        print('nfa1.accept_state.id:', nfa1.accept_state.id, 'nfa2.accept_state.id:', nfa2.accept_state.id)
        print('min_id:', min_id, 'max_id:', max_id)
        self.nfa.increment_state_ids(nfa1, left=min_id, right=max_id, increment=-1)
        for symbol, next_states in nfa2.start_state.transitions.items():
            for next_state in next_states:
                nfa1.accept_state.add_transition(symbol, next_state)

        # 从 self.states 中移除 nfa2.start_state
        self.nfa.states.remove(nfa2.start_state)  # 从状态列表中移除该状态
        self.nfa.state_count -= 1


        # 返回合并后的 NFA，nfa1 的终止状态变为 nfa2 的终止状态
        return self.build_nfa(nfa1.start_state, nfa2.accept_state)

    def build_nfa(self, start, accept):
        if self.nfa.start_state is None:
            self.nfa.start_state = start  # 确保起始状态为S0
        self.nfa.accept_state = accept  # 终止状态为编号最大的状态
        nfa = NFA()
        nfa.start_state = start
        nfa.accept_state = accept
        nfa.states = self.nfa.states
        for state in nfa.states:
            print(state.id, end=' ')
        print()
        return nfa


class DFAState:
    def __init__(self, id, nfa_states):
        self.id = id
        self.nfa_states = nfa_states  # NFA 状态的集合
        self.transitions = {}

    def add_transition(self, symbol, state):
        if symbol not in self.transitions:
            self.transitions[symbol] = state


class DFA:
    def __init__(self):
        self.states = []
        self.start_state = None
        self.accept_states = set()
        self.state_count = 0

    def new_state(self, nfa_states):
        state = DFAState(self.state_count, nfa_states)
        self.states.append(state)
        self.state_count += 1
        return state

    def visualize(self):
        dot = graphviz.Digraph()
        dot.attr(rankdir='LR')
        dot.graph_attr['dpi'] = '1000'

        # 创建一个隐式的起始节点，并且没有标签和形状
        dot.node("start", shape="none", label="")  # 隐式起点

        # 绘制起始状态
        dot.node(f"S{self.start_state.id}", shape='circle', label=f"S{self.start_state.id}")

        # 绘制从隐式起点指向S0的空箭头
        dot.edge("start", f"S{self.start_state.id}", label="Start")

        # 绘制终止状态
        for state in self.accept_states:
            dot.node(f"S{state.id}", shape='doublecircle', label=f"S{state.id}")

        # 绘制状态及其转移
        for state in self.states:
            for symbol, next_state in state.transitions.items():
                dot.edge(f"S{state.id}", f"S{next_state.id}", label=symbol)

        dot.render("dfa", format="png", cleanup=False)



def epsilon_closure(nfa, states):
    """计算给定状态集合的 epsilon 闭包"""
    stack = list(states)
    closure = set(states)

    while stack:
        state = stack.pop()
        if 'ε' in state.transitions:
            for next_state in state.transitions['ε']:
                if next_state not in closure:
                    closure.add(next_state)
                    stack.append(next_state)

    return closure


def move(nfa, states, symbol):
    """计算从给定状态集合出发，沿着给定符号的转移得到的状态集合"""
    new_states = set()
    for state in states:
        if symbol in state.transitions:
            for next_state in state.transitions[symbol]:
                new_states.add(next_state)
    return new_states


def nfa_to_dfa(nfa):
    """使用子集构造法将 NFA 转换为 DFA"""
    dfa = DFA()
    start_closure = epsilon_closure(nfa, {nfa.start_state})
    #we print the start_closure just to check whether it's right or not
    print('the start_closure includes:')
    for state in start_closure:
        print(state.id, end=' ')
    print()

    #we got the start_closure in nfa , which is going to be set as start_state of dfa, like wha I do below
    start_state = dfa.new_state(start_closure)
    dfa.start_state = start_state

    unmarked_states = [start_state]
    #we got lots of nfa_states in one closure, but to draw the final picture, we got to map them into dfa_state
    dfa_states_map = {frozenset(start_closure): start_state}

    while unmarked_states:
        current_state = unmarked_states.pop()
        current_closure = current_state.nfa_states

        print('the nfa_states of current_closure includes:')
        for state in current_closure:
            print(state.id, end=' ')
        print()

        # 检查是否包含 NFA 的接受状态，若包含则将其作为 DFA 的接受状态
        if nfa.accept_state in current_closure:
            dfa.accept_states.add(current_state)



        symbols = set()
        for state in current_closure:
            symbols.update(state.transitions.keys())

        for symbol in symbols - {'ε'}:  # 忽略 epsilon 转移
            move_result = move(nfa, current_closure, symbol)
            new_closure = epsilon_closure(nfa, move_result)

            if not new_closure:
                continue

            if frozenset(new_closure) not in dfa_states_map:
                new_state = dfa.new_state(new_closure)
                dfa_states_map[frozenset(new_closure)] = new_state
                unmarked_states.append(new_state)



            current_state.add_transition(symbol, dfa_states_map[frozenset(new_closure)])

    return dfa


# 测试部分
if __name__ == "__main__":
    regex = input("请输入正则表达式：")
    converter = RegexToNFAConverter(regex)
    nfa = converter.parse()

    print("正在生成 NFA 图像...")
    nfa.visualize()
    print("NFA 图像已保存为 nfa.png")

    print("正在将 NFA 转换为 DFA...")
    dfa = nfa_to_dfa(nfa)

    print("正在生成 DFA 图像...")
    dfa.visualize()
    print("DFA 图像已保存为 dfa.png")


#((ε|a)b*)*
#(a|b)*abb(a|b)*